package xinhao.lr.lr0;

import xinhao.*;
import java.util.*;

/**
 * @author by xinhao  2021/8/23
 * lr0 算法工具类
 */
public class LR0Utils {

    /**
     * 求解等价项目的集合
     * 对于任何 S -> a•Bb 的项目，因为圆点后面的是非终结符，
     * 那么这个非终结符 B 的产生式 B -> b B ->c
     * 对应的移入项目组  B -> •b B -> •c  都是相同项目，加入同一个项目集。
     * closure 方法就是计算项目集
     * @param items
     * @param grammar
     * @return
     */
    private static Set<ProductionItem> closure(Set<ProductionItem> items, Grammar grammar) {
        // 所有等价项目集合
        Set<ProductionItem> resultItems = new HashSet<>(items);
        Stack<ProductionItem> stack = new Stack<>();
        // 先将传入的items添加到栈里面
        stack.addAll(items);
        // 栈不为空，说明还有项目没有遍历到
        while (!stack.isEmpty()) {
            ProductionItem item = stack.pop();
            /**
             * 当前项目圆点位置是非终结符，那么这个非终结符的产生式组对应的移进项目和当前项目属于一个闭包
             */
            if (!item.getPosSymbol().isTerminator()) {
                // 非终结符对应的产生式组
                List<Production> productionList = grammar.getProductionsMap()
                        .get(item.getPosSymbol());
                for (Production production : productionList) {
                    // 创建产生式对应的项目
                    ProductionItem newItem = ProductionItem.createProduction(production);
                    /**
                     * 如果这个项目在 resultItems 中不包含，那么就添加
                     */
                    if (!resultItems.contains(newItem)) {
                        resultItems.add(newItem);
                        // 添加到栈中，新项目需要查找它的相同项目
                        stack.push(newItem);
                    }
                }
            }
        }
        return resultItems;
    }

    // 为 Goto 创建一个缓存 table，这样就只需要求解一次
    private static final Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> GOTO_TABLE = new HashMap<>();
    static ProductionItemSet Goto(ProductionItemSet itemSet, Symbol symbol, Grammar grammar) {
        // 如果缓存里有，那么直接返回，不用再求解了
        if (GOTO_TABLE.containsKey(itemSet)) {
            Map<Symbol, ProductionItemSet> map = GOTO_TABLE.get(itemSet);
            if (map.containsKey(symbol)) {
                return map.get(symbol);
            }
        }
        // 当前项目集 itemSet 遇到符号 symbol 的后继项目集合
        Set<ProductionItem> nextItems = new HashSet<>();
        for (ProductionItem item : itemSet.getItemSet()) {
            /**
             * 项目pos点的符号与 symbol 是否相同
             * 即项目 a•Bb 匹配 符号B
             * 后继项目就是 aB•b
             */
            if (item.getPosSymbol().equals(symbol)) {
                // 将后继项目添加到nextItems
                nextItems.add(ProductionItem.nextByItem(item));
            }
        }
        // 如果nextItems为空，说明当前项目集没有 符号symbol的后继项目
        if (nextItems.isEmpty()) {
            return null;
        }
        // 创建后继项目集
        ProductionItemSet gotoItemSet = ProductionItemSet.create(closure(nextItems, grammar));
        // 存放到缓存中
        Utils.addToDoubleMap(GOTO_TABLE, itemSet, symbol, gotoItemSet);
        return gotoItemSet;
    }

    /**
     * 得到当前文法所有的项目集
     * @param grammar
     * @return
     */
    private static List<ProductionItemSet> getAllItemSet(Grammar grammar) {
        // 文法中所有符号，包括终结符和非终结符，但是不包括结束符号 END
        Set<Symbol> allSymbol = grammar.getAllSet();
        Symbol start = grammar.getStart();
        // 开始符号只有一个产生式，这里用到增广文法
        Production startProduction = grammar.getProductionsMap().get(start).get(0);
        // 开始符号产生式对应的移进项目
        ProductionItem startItem = ProductionItem.createProduction(startProduction);
        // 开始符号对应的项目集，也是第一个项目集
        ProductionItemSet startItemSet = ProductionItemSet.create(closure(Utils.asSet(startItem), grammar));

        // 当前文法所有的项目集
        List<ProductionItemSet> allItemSetList = new ArrayList<>();
        allItemSetList.add(startItemSet);
        // 通过栈来遍历所有的项目集，得到项目集对所有符号产生的新的项目集
        Stack<ProductionItemSet> stack = new Stack<>();
        stack.push(startItemSet);
        while (!stack.isEmpty()) {
            ProductionItemSet itemSet = stack.pop();
            // 遍历所有符号
            for (Symbol eachSymbol : allSymbol) {
                // 当前项目集遇到字符eachSymbol得到后继项目集
                ProductionItemSet gotoItemSet = Goto(itemSet, eachSymbol, grammar);
                /**
                 * 如果得到的后继项目集gotoItemSet 在allItemSetList中没有，
                 * 那么代表它是全新的，那么添加进行。
                 */
                if (gotoItemSet != null && !allItemSetList.contains(gotoItemSet)) {
                    allItemSetList.add(gotoItemSet);
                    // 新的项目集要添加到栈中，进行遍历
                    stack.push(gotoItemSet);
                }
            }
        }
        return allItemSetList;
    }

    /**
     * 得到文法对应的 LR0 分析表 actionMap 和 gotoMap
     * @param grammar
     * @param allItemSetList
     * @param actionMap
     * @param gotoMap
     */
    private static void createLR0Table(Grammar grammar, List<ProductionItemSet> allItemSetList,
                                       Map<ProductionItemSet, Map<Symbol, Action>> actionMap,
                                       Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap) {
        // 开始符号
        Symbol start = grammar.getStart();
        // 所有的非终结符
        Set<Symbol> vtSymbols = grammar.getVtSet();
        // 将结束符号添加进去
        vtSymbols.add(Symbol.END);
        // 遍历文法所有的项目集
        for (ProductionItemSet itemSet : allItemSetList) {
            // 遍历项目集中的项目
            for (ProductionItem item : itemSet.getItemSet()) {
                // 得到当前项目 pos 位置的符号
                Symbol posSymbol = item.getPosSymbol();
                // 如果是非终结符，那么就要添加到 gotoMap 中
                if (!posSymbol.isTerminator()) {
                    Utils.addToDoubleMapPrintConflict(gotoMap, itemSet, posSymbol, LR0Utils.Goto(itemSet, posSymbol, grammar),
                            "gotoMap 有冲突: old: %s, new: %s");
                } else {
                    // 是终结符但不是结束符号 END
                    if (!Symbol.END.equals(posSymbol)) {
                        // 获取后继项目集
                        ProductionItemSet nextItemSet = LR0Utils.Goto(itemSet, posSymbol, grammar);
                        // 想 action 中添加移入操作action
                        Utils.addToDoubleMapPrintConflict(actionMap, itemSet, posSymbol, Action.createS(nextItemSet),
                                "actionMap 有冲突: old: %s,  new: %s");
                    } else {
                        // 当前项目是 aBb• 格式，说明需要归约，这个就是归约需要的产生式
                        Production production = item.getProduction();
                        // 如果产生式左部和开始符号相同，说明是总结了，添加 acc 的action
                        if (start.equals(production.getLeft())) {
                            Utils.addToDoubleMapPrintConflict(actionMap, itemSet, posSymbol, Action.createAcc(),
                                    "actionMap 有冲突: old: %s,  new: %s");
                        } else {
                            /**
                             * 在LR0 算法中，对于  aBb• 这类项目，只要它对应的产生式不是开始符号的产生式
                             * 那么遇到任意终结符包括终止符号$ 都进行归约。
                             * 但是这种方式是会有冲突的，例如:
                             * 1. 对于同一个项目集 itemSet 中有两个项目 S-> a• 和 S-> a•b,
                             *    遇到终结符b，那么既可以归约，又可以移入，这就是移入-归约冲突
                             * 2. 对于同一个项目集 itemSet 中有两个项目 S-> a• 和 A-> b•
                             *    两个项目都可以归约，但是归约的产生式不同，这个时候就是归约-归约冲突
                             */
                            for (Symbol symbol : vtSymbols) {
                                Utils.addToDoubleMapPrintConflict(actionMap, itemSet, symbol, Action.createR(production),
                                        "actionMap 有冲突: old: %s,  new: %s");
                            }
                        }
                    }
                }
            }
        }
    }

    /**
     * 判断文法能否匹配这个输入符号串inputSymbols
     * @param inputSymbols
     * @param startState
     * @param actionMap
     * @param gotoMap
     * @return
     */
    private static boolean match(List<Symbol> inputSymbols, ProductionItemSet startState,
                              Map<ProductionItemSet, Map<Symbol, Action>> actionMap,
                              Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap) {
        // 匹配的产生式列表
        List<Production> matchProductions = new ArrayList<>();
        // 状态栈
        Stack<ProductionItemSet> stateStack = new Stack<>();
        // 放入开始状态，即开始项目集
        stateStack.push(startState);
        // 符号栈
        Stack<Symbol> symbolStack = new Stack<>();
        // 先放入结束符号$
        symbolStack.push(Symbol.END);

        // 表示读取输入符号的位置
        int inputPos = 0;
        while (true) {
            // 当前状态栈栈顶状态
            ProductionItemSet currentItemSet = stateStack.peek();
            // 当然输入字符
            Symbol inputSymbol = inputSymbols.get(inputPos);
            // 获取当前栈顶状态遇到输入符号得到的 action
            Action action = actionMap.get(currentItemSet).get(inputSymbol);
            // 如果是 acc
            if (action.isAcc()) {
                // 当输入字符是最后一个字符，表示匹配成功。否则输入字符还没有匹配完成，匹配失败
                if (inputPos == inputSymbols.size() -1) {
                    System.out.println("匹配成功");
                    System.out.println(matchProductions);
                    return true;
                }
                System.out.println("匹配失败");
                System.out.println(matchProductions);
                return false;
            } else if (action.isS()) {
                // 移入操作
                stateStack.push(action.getStateItemSet());
                symbolStack.push(inputSymbol);
                // 下一个输入字符
                inputPos ++;
            } else if (action.isR()){
                // 归约操作的产生式
                Production production = action.getProduction();
                int size = production.getRight().size();
                // 记录一下状态栈弹出的状态
                List<Integer> popStateList = new ArrayList<>();
                // 记录一下弹出的字符
                List<Symbol> popSymbol = new ArrayList<>();
                // 根据产生式右部的字符数量，从状态栈和字符栈中弹出对应数量的元素
                for (int index = 0; index < size; index++) {
                    popStateList.add(stateStack.pop().getState());
                    popSymbol.add(symbolStack.pop());
                }
                System.out.println("popStateList: " + popStateList + "  popSymbol:"+popSymbol+"  production:"+production);
                // 添加归约的产生式
                matchProductions.add(production);

                // 将产生式左部添加到字符栈
                symbolStack.push(production.getLeft());
                // 获取这个字符在 gotoMap 中对应的状态，添加到状态栈
                ProductionItemSet itemSet = gotoMap.get(stateStack.peek()).get(production.getLeft());
                stateStack.push(itemSet);
            } else {
                throw new RuntimeException("匹配错误");
            }
        }
    }


    public static void main(String[] agrs) {
        Symbol start = Alphabet.addSymbol("S'");
        Grammar grammar = Grammar.create(start,
                Production.create(start, "S"),
                Production.create(Alphabet.getSymbol("S"), "BB"),
                Production.create(Alphabet.getSymbol("B"), "aB"),
                Production.create(Alphabet.getSymbol("B"), "b")
                );

        List<ProductionItemSet> allItemSetList = getAllItemSet(grammar);
        System.out.println(allItemSetList);

        Map<ProductionItemSet, Map<Symbol, Action>> actionMap = new HashMap<>();
        Map<ProductionItemSet, Map<Symbol, ProductionItemSet>> gotoMap = new HashMap<>();
        createLR0Table(grammar, allItemSetList, actionMap, gotoMap);

        List<Symbol> inputSymbols = Utils.createSymbolsByString("bab");
        inputSymbols.add(Symbol.END);
        match(inputSymbols, allItemSetList.get(0), actionMap, gotoMap);
    }
}
